<!DOCTYPE html>
<html lang="zh">

<head>
  <link rel="stylesheet" href="css/prism.css">
  <style>
    html,
    body {
      box-sizing: border-box;
      margin: 0;
      padding: 0;
      height: 100%;
      font-size: 12px;
    }

    body {
      min-height: 500px;
    }

    section {
      display: flex;
      flex-wrap: wrap;
    }

    .code {
      margin-top: 3px;
    }

    pre[class*=language-] {
      margin: 0;
      padding: 0;
    }

    main {
      border-top: 2px solid #ccc;
      width: 100%;
      height: 66%;
      min-height: 400px;
    }
  </style>
  <title>优先级队列(有序数组)</title>
</head>

<body>
  <section class="frames"></section>
  <div class="code" style="display: none;">
    <pre><code class="language-java">public static int binarySearch(int[] a, int target) {
    int i = 0, j = a.length - 1;
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {          // 在左边
            j = m - 1;
        } else if (a[m] < target) {   // 在右边
            i = m + 1;
        } else {
            candidate = m;
            j = m - 1;
        }
    }
    return candidate;
}</code></pre>
  </div>
  <main></main>
  <section>
    <div style='background-color:#cc99cd; margin: 2px 2px 0 0; padding: 4px 6px;'>索引</div>
    <div style='background-color:#67cdcc; margin: 2px 2px 0 0; padding: 4px 6px;'>数据</div>
    <div style='background-color:#f08d49; margin: 2px 2px 0 0; padding: 4px 6px;'>比较或交换</div>
  </section>
  <div style='margin: 2px 2px 0 0; padding: 4px 6px;'>
    <div style="margin-bottom: 2px;">
      <span>初始队列&nbsp;</span><input type="text" id='initQueue' class="saveable" value="1,4,5,8,10">
    </div>
    <div style="margin-bottom: 2px;">
      <span>入队&nbsp;</span><input type="text" id='offered' class="saveable" value="3">
      <input style='font-size:12px;' type="button" value="offer()" onclick="offer()">
    </div>
    <div style="margin-bottom: 2px;">
      <span>出队&nbsp;</span><input style='font-size:12px;' type="button" value="poll()" onclick="poll()">
    </div>
    <span>动画速度(ms)&nbsp;</span><input type="number" step="100" value="300" id="animate_speed" class="saveable">
    <input style='font-size:12px;' type="button" value="保存" onclick="onSave('priority_quque_2')">
  </div>
  <script src="js/p5.js"></script>
  <script src="js/p5-svg.js"></script>
  <script src="js/util.js"></script>
  <script src="js/prism.js"></script>
  <script>
    function poll() {
      d.add({ array: dataArray, highlights: [dataArray.length - 1] }, frame)
      dataArray.pop()
      d.add({ array: dataArray }, frame)
      d.updateFrameButtons()
    }

    function swap(a, i, j) {
      let k = a[i]
      a[i] = a[j]
      a[j] = k
    }

    function offer() {
      const offered = Number(document.querySelector('#offered').value)
      let i = dataArray.length - 1
      while (i >= 0 && dataArray[i] > offered) {
        d.add({ array: i == dataArray.length - 1 ? [...dataArray, ''] : dataArray, highlights: [i], pointers: [{ index: i, text: 'i' }] }, frame)
        dataArray[i + 1] = dataArray[i]
        d.add({ array: dataArray, highlights: [i + 1], pointers: [{ index: i, text: 'i' }] }, frame)
        i--
      }
      d.add({ array: dataArray, pointers: [{ index: i, text: 'i' }] }, frame)
      dataArray[i + 1] = offered
      d.add({ array: dataArray, highlights: [i + 1], pointers: [{ index: i, text: 'i' }] }, frame)
      d.add({ array: dataArray }, frame)
      d.updateFrameButtons()
    }
    const options = loadOptionsFromStorage('priority_quque_2')
    const DIAMETER = 30                   // 直径
    const RECT_HEIGHT = 30                // 值矩形高度
    const SPACING = 1                     // 间隙
    const INDEX_RECT_HEIGHT = 20          // 索引矩形高度
    const POINTER_HEIGHT = 150            // 指针高度, 从底部算
    const d = new Draw(options.animate_speed)
    const NODE_LEFT_PAD = 250
    const LEFT_PAD = 20
    const TOP_PAD = 40

    let dataArray = options.initQueue.split(',').map(e => Number(e))
    function preload() {
      // const font = loadFont('JetBrainsMono-Regular.ttf')
    }
    function setup() {
      const WIN_WIDTH = document.querySelector('main').clientWidth
      const WIN_HEIGHT = document.querySelector('main').clientHeight
      const FONT_SIZE = 10
      createCanvas(WIN_WIDTH, WIN_HEIGHT, SVG)
      textSize(FONT_SIZE)
      textAlign(CENTER)
      d.add({ array: dataArray }, frame)
      d.updateFrameButtons()
    }
    function draw() {
      d.draw(() => background('#2d2d2d'))
    }

    /*
      array: 数组
      pointers: 指针
      highlights: 高亮位置
      lineNumber: 高亮行号
    */
    function frame({ array, pointers, highlights, lineNumber }) {
      const pre = document.querySelector('pre')
      if (lineNumber > 0) {
        pre.setAttribute('data-line', lineNumber)
        Prism.highlightAllUnder(pre)
      }

      let x = LEFT_PAD, y = height - TOP_PAD - DIAMETER / 2
      for (let i = 0; i < array.length; i++) {
        stroke(255)
        pointers.draw2(i, y, x + DIAMETER)
        noStroke()

        highlights.includes(i) ? fill('#f08d49') : fill('#67cdcc')
        rect(x + DIAMETER, y, DIAMETER, DIAMETER)
        fill('#ffffff')
        text(array[i], x + DIAMETER + DIAMETER / 2, y + DIAMETER / 2 + 4)

        fill('#cc99cd')
        rect(x, y, DIAMETER, DIAMETER)
        fill('#ffffff')
        text(i, x + DIAMETER / 2, y + DIAMETER / 2 + 4)

        y -= DIAMETER
      }
    }
  </script>
</body>

</html>